package com.rgs.se.sort;


import java.util.HashMap;
import java.util.Map;

/**
 * @author Ren Gaoshuai
 * @ClassName TestSort
 * @Description TODO
 * @date 2021-11-26 9:13
 **/
public class TestSort {

    public static int[] Temp(int[] arr,int a,int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
        return arr;
    }

    public static void Print(int[] arr){
        for(int i = 0;i<arr.length;i++){
            System.out.print(arr[i]+",");
        }
        System.out.println();
    }

    /**
     * 双向指针快速排序
     */
    public void quickSort(int[] a,int low,int high){
        if (low >= high){
            return ;
        }
        int i = low;
        int j = high;
        int k = a[low];

        while(i < j){
            while(a[j] >= k && i < j){
                j--;
            }
            Temp(a,i,j);

            while(a[i] <= k && i < j){
                i++;
            }
            Temp(a,i,j);

        }
        quickSort(a,low,i-1);
        quickSort(a,i+1,high);
    }

    /**
     *     自顶向下的归并，可读性较好
     */
    public void mergeSort(int[] a,int low,int high){
        if (low < high) {
            //递归分解,右移一位，相当除2，小了一倍
            int mid = (low + high) >> 1;
            mergeSort(a, low, mid);
            mergeSort(a, mid + 1, high);
            //合并
            merge(a, low, mid, high);
        }
    }
    //将两个子序列归并成一个子序列
    public void merge(int[] a,int low,int mid,int high){
        int[] temp = new int[a.length];
        int pa = low;
        int pb = mid+1;
        int pt = 0;

        while(pa <= mid && pb <= high){
            if (a[pa] < a[pb]){
                temp[pt] = a[pa];
                pa++;
                pt++;
            }else{
                temp[pt] = a[pb];
                pb++;
                pt++;
            }
        }

        //处理数据有剩余
        //pa有剩余
        while(pa <= mid){
            temp[pt] = a[pa];
            pa++;
            pt++;
        }
        //pb有剩余
        while(pb <= high){
            temp[pt] = a[pb];
            pb++;
            pt++;
        }
        for (int i = 0 ; i < pt ; i++){
            a[low+i] = temp[i];
        }
    }

    /**
     * 快速排序 2，分割递归
     */
    public void quickSort2(int[] a,int low,int high){
        if (low < high){
            //返回基准的位置
            int i = this.partition(a,low,high);
            quickSort2(a,low,i-1);
            quickSort2(a,i+1,high);
        }
    }
    public int partition(int[] a,int low,int high){
        //找到基准的位置
        int i = low;
        int j = high;
        int k = a[low];
        while(i <= j){
            //从左到右
            while(a[j] >= k && i < j){
                j--;
            }
            a[i] = a[j];

            //从右到左
            while(a[i] <= k && i < j){
                i++;
            }
            a[j] = a[i];
        }

        a[i] = k;

        return i;
    }

    /**
     *     二分查找  （分治法）
     */
    public int binSercah(int[] a,int low,int high,int key){
        if (low <= high){
            int mid = (high+low) >> 1;
            if (a[mid] == key){
                return mid;
            }else if (a[mid] > key){
                return binSercah(a,low,mid-1,key);
            }else{
                return binSercah(a,mid+1,high,key);
            }
        }else{
            return -1;
        }

    }

    /**
     *     第k小的元素  （分治法，快排思想，基准定位）
     */
    public int kmin(int[] a,int low,int high,int k){
        int i = low;
        int j = high;
        int p = a[low]; //基准

        if (low < high){
            while(i != j){
                while(a[j] > p){
                    j--;
                }
                Temp(a,i,j);
                while(a[i] < p){
                    i++;
                }
                Temp(a,i,j);
            }

            //i 这个下标就是已经排好序的下标，下边为0 k=1  下标1 k=2
            if (k-1 == i){
                return a[i];
            }else if (k-1 < i){
                //左边
                return kmin(a,low,i-1,k);
            }else{
                //右边
                return kmin(a,i+1,high,k);
            }
        }else if(low == high && low == k-1){
            return a[k-1];
        }
        else {
            return -1;
        }

    }


    /**
     * 最大逆序对和
     */
    public static int max = 0;  //存最大和
    public static Map<String,Object> map = new HashMap<>(8);  //存最大的逆序对字符串
    //递归（分解序列）
    public void mergeSort2(int[] a,int low,int high){
        if (low < high) {
            //递归分解,右移一位，相当除2，小了一倍
            int mid = (low + high) >> 1;
            mergeSort2(a, low, mid);
            mergeSort2(a, mid + 1, high);
            //合并
            merge2(a, low, mid, high);
        }
    }
    //归并（合并序列）
    public void merge2(int[] a,int low,int mid,int high){
        int[] temp = new int[a.length];
        int pa = low;
        int pb = mid+1;
        int pt = 0;

        while(pa <= mid && pb <= high){
            if (a[pa] < a[pb]){
                temp[pt] = a[pa];
                pa++;
                pt++;
            }else{
//                可以求出所有的逆序对。
//                for (int i = pa; i <= mid; i++) {
//                    map.put("max",a[i]+ a[pb]);
//                    map.put("value","("+a[i]+","+a[pb]+")");
//                }
                //优化，直接加上左序列的末尾元素（末尾元素最大）
                if (a[mid]+ a[pb] > (Integer) map.get("max")){
                    map.put("max",a[mid]+ a[pb]);
                    map.put("value","("+a[mid]+","+a[pb]+")");
                }
                temp[pt] = a[pb];
                pb++;
                pt++;
            }
        }
        //处理数据有剩余
        //pa有剩余
        while(pa <= mid){
            temp[pt] = a[pa];
            pa++;
            pt++;
        }
        //pb有剩余
        while(pb <= high){
            temp[pt] = a[pb];
            pb++;
            pt++;
        }
        for (int i = 0 ; i < pt ; i++){
            a[low+i] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] a = {2,5,1,7,10,6,9,4,3,8};
        int[] b = {5,9,3,6,8,10,1,4};
        TestSort testSort = new TestSort();


//        System.out.println("排序前：");
//        Print(a);
//
//        System.out.println("排序后：");
//        Print(a);
        System.out.println("源数组：");
        Print(b);
        testSort.mergeSort2(b,0,b.length-1);
        System.out.println(map.get("max"));
        System.out.println(map.get("value"));
    }


}
